/**
 * @file 字符串逆序
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-11
 * 
 * @copyright Copyright (c) 2021
 * 
 * 344.反转字符串
 * 541.反转字符串II
 * 151.翻转字符串里的单词 -- 原地逆序
 * 557.反转字符串中的单词III -- 151.子问题
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <unistd.h>
#include <vector>
using namespace std;

class Solution
{
public:
    // 344.
    void reverseString(vector<char> &s)
    {
        int i = 0, j = s.size() - 1;
        while (i < j) {
            swap(s[i++], s[j--]);
        }
    }
    // 541.
    string reverseStr(string s, int k)
    {
        for (int i = 0; i < s.size(); i += 2 * k) {
            k = min(k, (int)(s.size() - i));
            reverseString(s, i, i + k - 1);
        }
        return s;
    }
    // 151.
    string reverseWords(string s)
    {
        // 解法一：倒序遍历s，遍历到空格就把当前段加入答案
        // 解法二：原地逆序
        removeExtraSpaces(s);
        int i = 0, j = s.size() - 1;
        reverseString(s, i, j);
        int start = i;
        while (i <= j) {
            while (s[i] == ' ' || i == j) {
                int end = i == j ? j : i - 1;
                reverseString(s, start, end);
                ++i;
                start = i;
            }
            ++i;
        }
        return s;
    }
    // 557.
    string reverseWords557(string s)
    {
        int i = 0, j = s.size() - 1;
        int start = i;
        while (i <= j) {
            while (s[i] == ' ' || i == j) {
                int end = i == j ? j : i - 1;
                reverseString(s, start, end);
                ++i;
                start = i;
            }
            ++i;
        }
        return s;
    }

private:
    void reverseString(string &s, int i, int j)
    {
        while (i < j) {
            swap(s[i++], s[j--]);
        }
    }
    // 移除冗余空格：使用双指针（快慢指针法）O(n)的算法
    void removeExtraSpaces(string &s)
    {
        int i = 0, j = 0; // 定义快指针，慢指针
        // 去掉字符串前面的空格
        while (s.size() > 0 && j < s.size() && s[j] == ' ') {
            j++;
        }
        for (; j < s.size(); j++) {
            // 去掉字符串中间部分的冗余空格
            if (j - 1 > 0 && s[j - 1] == s[j] && s[j] == ' ') {
                continue;
            } else {
                s[i++] = s[j];
            }
        }
        if (i - 1 > 0 && s[i - 1] == ' ') { // 去掉字符串末尾的空格
            s.resize(i - 1);
        } else {
            s.resize(i); // 重新设置字符串大小
        }
    }
};

Solution solve = Solution();

void test541()
{
    string s = "abcdefg";
    int k = 8;
    cout << solve.reverseStr(s, k) << endl;
}

void test151()
{
    string s = "  a  good    example  ";
    cout << solve.reverseWords(s) << endl;
}

int main()
{
    // test541();
    test151();
    return 0;
}